#ifndef __input_generation__
#define __input_generation__

/*
Functions useful for input generation

Author: Jyrki Katajainen
Email: jyrki@diku.dk
Version: $Revision: 1.1 $
Date: $Date: 2003/08/31 19:39:09 $
*/

#include <cstdlib> // defines std::rand and std::srand
#include <iterator> // defines std::iterator_traits

template <typename input_iterator>
void
increasing_sequence(input_iterator first, input_iterator past_the_end) {
  typedef typename std::iterator_traits<input_iterator>::value_type value_type;
  input_iterator q;  
  for (q = first; q != past_the_end; ++q) {
    *q = static_cast<value_type>(q - first); 
  }
}

template <typename input_iterator>
void
decreasing_sequence(input_iterator first, input_iterator past_the_end) {
  typedef typename std::iterator_traits<input_iterator>::value_type value_type;
  input_iterator q;  
  for (q = first; q != past_the_end; ++q) {
    *q = static_cast<value_type>(past_the_end - q); 
  }
}

template <typename input_iterator>
void
zero_sequence(input_iterator first, input_iterator past_the_end) {
  typedef typename std::iterator_traits<input_iterator>::value_type value_type;
  input_iterator q;  
  for (q = first; q != past_the_end; ++q) {
    *q = static_cast<value_type>(0); 
  }
}

template <typename input_iterator>
void
random_sequence(input_iterator first, input_iterator past_the_end) {
  typedef typename std::iterator_traits<input_iterator>::value_type value_type;
  input_iterator q;  
  for (q = first; q != past_the_end; ++q) {
    *q = static_cast<value_type>(std::rand()); 
  }
}

template <typename input_iterator, typename integer>
void
random_sequence (
  input_iterator first, 
  input_iterator past_the_end, 
  integer lower_bound,
  integer upper_bound,  // half-open interval, e.g., [0..2) 
  integer additive_term = 0
) {
  typedef typename std::iterator_traits<input_iterator>::value_type value_type;
  input_iterator q;  
  for (q = first; q != past_the_end; ++q) {
    integer v = static_cast<integer>(std::rand());
    v = (v % (upper_bound - lower_bound)) + lower_bound + additive_term;
    *q = value_type(v); 
  }
}

template <typename input_iterator>
void
binary_sequence(input_iterator first, input_iterator past_the_end) {
  typedef typename std::iterator_traits<input_iterator>::value_type value_type;
  input_iterator q;  
  for (q = first; q != past_the_end; ++q) {
    *q = static_cast<value_type>(std::rand() % 2); 
  }
}

template <typename random_access_iterator>
void permute ( 
  random_access_iterator first,
  random_access_iterator past_the_end,
  unsigned long seed = 4321
) {
  random_access_iterator p;
  random_access_iterator q;
  std::srand(seed);
  for (q = past_the_end - 1; q > first; --q) {
    p = first + (std::rand() % (q - first + 1));
    std::swap(*p, *q);
  }
}

#endif // __input_generation__
